题目分析
来一道简单题目给小伙伴们放松放松,小伙伴们能优化到什么程度呢?能否在$O(n)$的时间复杂度内完成?能否在$O(1)$的空间复杂度完成?如果可以能否同时满足两个要求呢?
排序求解
因为数组中主要元素超过一半,因此我们将数组进行排序后,连续长度一定超过数组长度的一半。我们从0号元素遍历到nums.size() - num.size() / 2,如果存在nums[i] == nums[i + num.size() / 2]说明该元素是主要元素,否则返回-1。
主要时间在数组的排序,算法的**时间复杂度为$O(nlog(n))$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
哈希表
最简单的方法是哈希表求解,我们将元素都存放在哈希表中,然后遍历哈希表,如果存在某个元素的个数大于数组长度的一半,那么说明该元素是主要元素。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
摩尔投票法
这个题目的最优解是摩尔投票法,是一种特殊算法,其思想是主要元素的个数超过其他所有元素之和,因此用一个计数器记录当前获胜者的票数。
如果当前获胜者是A,票数是k,如果下一个选票是B,那么k–,如果下一个选票是A,那么k++。一旦k=0,就没有获胜者。最后投票完成后,如果存在主要元素,那么获胜者一定是主要元素。如果不存在主要元素,获胜者可能是其他元素。
如何理解呢?假设A是主要元素,那么A的选票足以大于其他的所有人,因此无论如何抵消,A都会在最后胜出。因此我们可以用一次遍历确定获胜者,然后再用一次遍历统计获胜者的票数即可。如果票数大于数组长度的一半则为主要元素,否则没有主要元素。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
刷题总结
这个题目难度很小,想给小伙伴们多科普一些特殊算法,拓展视野。